package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.TreeNode;

import java.util.HashMap;
import java.util.Map;


public class No106buildTree {
    public static void main(String[] args) {
        TreeNode ret = buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
        System.out.println("[" + ret + "]");
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length) {
            return null;
        }
        for(int i=0;i<inorder.length;i++){
            inOrderMap.put(inorder[i], i);
        }
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private static Map<Integer, Integer> inOrderMap = new HashMap<>();

    public static TreeNode buildTree(int[] inorder, int iStartIndex, int iEndIndex, int[] postorder, int pStartIndex, int pEndIndex) {
        if (iStartIndex < 0 || iStartIndex > iEndIndex || iEndIndex >= inorder.length) {
            return null;
        }
        TreeNode ret = new TreeNode(postorder[pEndIndex]);
        if (iStartIndex == iEndIndex) {
            return ret;
        }
        int root = postorder[pEndIndex];
        int rootInOrderIndex = inOrderMap.get(root);

        int pOrderIndex = pStartIndex + rootInOrderIndex - iStartIndex;
        ret.left = buildTree(inorder, iStartIndex, rootInOrderIndex - 1, postorder, pStartIndex, pOrderIndex - 1);
        ret.right = buildTree(inorder, rootInOrderIndex + 1, iEndIndex, postorder, pOrderIndex, pEndIndex - 1);
        return ret;
    }
}
